package com.xiaokan.agent;

import java.util.ArrayList;
import java.util.List;

import com.xiaokan.model.Configuration;
import com.xiaokan.model.Move;

public class CheckerAgentThread extends Thread {

	private long nodes = 0;
	private volatile Configuration config;
	private byte agentSide, humanSide;
	private int maxDepth = 2;
	private Move stack[] = new Move[3];
	private int ptr = 0;
	// private BufferedWriter out;
	private int level;
	public final static int EASY = 2, MEDIUM = 5, HARD = 8, SUPERHARD = 12;

	private Object bestAction = null;

	private List<List<Move>> jumps = new ArrayList<List<Move>>();
	private Move moves[][][][] = new Move[8][8][8][8];

	public final void result(Object o, byte side) {
		// assert config.config[4][3] == 2;
		// assert o != null;
		if (o instanceof Move) {
			// single one-step move
			Move m = (Move) o;

			assert config.config[m.fromX][m.fromY] == side;
			assert config.config[m.toX][m.toY] == 0;

			config.config[m.toX][m.toY] = config.config[m.fromX][m.fromY];
			config.config[m.fromX][m.fromY] = 0;

		} else if (o instanceof List<?>) {

			List<Move> list = (List<Move>) o;
			Move start = list.get(0);
			int fromX = start.fromX, fromY = start.fromY;
			assert config.config[fromX][fromY] == side;
			for (int i = 0; i < list.size(); i++) {
				Move m = list.get(i);
				int midX = (m.fromX + m.toX) >> 1, midY = (m.fromY + m.toY) >> 1;
				assert config.config[midX][midY] == 3 - side;
				config.config[midX][midY] = 0;
			}
			Move end = list.get(list.size() - 1);
			int toX = end.toX, toY = end.toY;
			assert (config.config[toX][toY] == 0);
			config.config[toX][toY] = config.config[fromX][fromY];
			config.config[fromX][fromY] = 0;
		}

		// if (config.config[4][3] != 2) {
		// Move m = (Move) o;
		// System.out.format("%d %d %d %d\n", m.fromX, m.fromY, m.toX, m.toY);
		// }
		// assert config.config[4][3] == 2;
	}

	public final void recover(Object o, byte side) {
		// assert config.config[4][3] == 2;
		assert o != null;
		if (o instanceof Move) {

			// recover single one-step move
			Move m = (Move) o;
			assert config.config[m.fromX][m.fromY] == 0;
			assert config.config[m.toX][m.toY] == side;

			config.config[m.fromX][m.fromY] = config.config[m.toX][m.toY];
			config.config[m.toX][m.toY] = 0;

		} else if (o instanceof List<?>) {
			// recover a series of jumps
			List<Move> list = (List<Move>) o;
			Move start = list.get(0);
			int fromX = start.fromX, fromY = start.fromY;
			assert config.config[fromX][fromY] == 0;
			for (int i = 0; i < list.size(); i++) {
				Move m = list.get(i);
				int midX = (m.fromX + m.toX) >> 1, midY = (m.fromY + m.toY) >> 1;
				assert (config.config[midX][midY] == 0);
				config.config[midX][midY] = 3 - side;
			}
			Move end = list.get(list.size() - 1);
			int toX = end.toX, toY = end.toY;
			assert config.config[toX][toY] == side;
			config.config[fromX][fromY] = config.config[toX][toY];
			config.config[toX][toY] = 0;
		}
		// assert config.config[4][3] == 2;
	}

	/**
	 * 
	 * @return the one-step diagonal moves it could move
	 */
	private List<Move> getMoves(byte side) {
		List<Move> list = new ArrayList<Move>(12);
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				if (config.config[i][j] == side) {
					switch (side) {
					case 1:
						int x = i + 1,
						y = j - 1;
						if (isLegal(x, y) && config.config[x][y] == 0) {
							list.add(moves[i][j][x][y]);
						}
						x = i + 1;
						y = j + 1;
						if (isLegal(x, y) && config.config[x][y] == 0) {
							list.add(moves[i][j][x][y]);
						}
						break;
					case 2:
						x = i - 1;
						y = j - 1;
						if (isLegal(x, y) && config.config[x][y] == 0) {
							list.add(moves[i][j][x][y]);
						}
						x = i - 1;
						y = j + 1;
						if (isLegal(x, y) && config.config[x][y] == 0) {
							list.add(moves[i][j][x][y]);
						}
						break;
					}

				}
		return list;
	}

	public void jump(int i, int j, byte side) {
		boolean flag = true;

		/**
		 * flag = true <-> unable to jump, save these jumps
		 */

		switch (side) {
		case 1:
			int x = i + 2,
			y = j - 2;
			int midX = i + 1,
			midY = j - 1;
			if (isLegal(x, y) && config.config[midX][midY] == 2 && config.config[x][y] == 0) {
				// push
				stack[ptr++] = moves[i][j][x][y];
				jump(x, y, side);
				// pop
				ptr--;
				flag = false;
			}

			x = i + 2;
			y = j + 2;
			midX = i + 1;
			midY = j + 1;
			if (isLegal(x, y) && config.config[midX][midY] == 2 && config.config[x][y] == 0) {
				// push
				stack[ptr++] = moves[i][j][x][y];
				jump(x, y, side);
				// pop
				ptr--;
				flag = false;
			}
			break;

		case 2:
			x = i - 2;
			y = j - 2;
			midX = i - 1;
			midY = j - 1;
			if (isLegal(x, y) && config.config[midX][midY] == 1 && config.config[x][y] == 0) {
				// push
				stack[ptr++] = moves[i][j][x][y];
				jump(x, y, side);
				// pop
				ptr--;
				flag = false;
			}

			x = i - 2;
			y = j + 2;
			midX = i - 1;
			midY = j + 1;
			if (isLegal(x, y) && config.config[midX][midY] == 1 && config.config[x][y] == 0) {
				// push
				stack[ptr++] = moves[i][j][x][y];
				jump(x, y, side);
				// pop
				ptr--;
				flag = false;
			}
			break;
		}
		// no more jumps, save jumps;
		if (flag) {
			if (ptr > 0) {
				List<Move> list = new ArrayList<Move>();
				for (i = 0; i < ptr; i++) {
					list.add(stack[i]);
				}
				jumps.add(list);
			}
		}
	}

	public void getJumps(byte side) {
		if (jumps.size() != 0)
			jumps.clear();
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				if (config.config[i][j] == side)
					jump(i, j, side);
	}

	public void reset() {
		config.init();
		bestAction = null;
	}

	private void action() {
		// find actions
		bestAction = null;
		max(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
		result(bestAction, agentSide);

	}

	public int max(int alpha, int beta, int depth) {
		// cut-off test
		nodes++;
		
		if (nodes % 10000000 == 0)
			System.out.println(nodes);
		if (depth > maxDepth) {
			return utility();
		}
		// try {
		// out.write(depth + "\n");
		// } catch (IOException e) {
		// e.printStackTrace();
		// }
		int v = Integer.MIN_VALUE;
		if (testTerminal()) {
			return utility();
		}

		getJumps(agentSide);
		List<Move> moves = null;
		List<List<Move>> jumpsList = null;
		if (jumps.size() == 0)
			moves = getMoves(agentSide);
		else
			jumpsList = jumpsClone();
		// single one-step move
		if (moves != null)
			for (Move m : moves) {
				// make action
				result(m, agentSide);
				// printCheckerBoard("Max", currentConfig);
				int tempV = min(alpha, beta, depth + 1);

				// recover action
				recover(m, agentSide);
				if (tempV > v) {
					v = tempV;
					if (depth == 0) {
						bestAction = m;
					}
				}
				if (v >= beta)
					return v;
				if (v > alpha)
					alpha = v;
			}
		// a series of jumps
		if (jumpsList != null)
			for (List<Move> jump : jumpsList) {
				// make action
				result(jump, agentSide);
				// printCheckerBoard("Max", currentConfig);
				int tempV = min(alpha, beta, depth + 1);
				// recover action
				recover(jump, agentSide);
				if (tempV > v) {
					v = tempV;
					if (depth == 0) {
						bestAction = jump;
					}
				}
				if (v >= beta)
					return v;
				if (v > alpha)
					alpha = v;
			}

		// has no moves
		if ((moves == null || moves.size() == 0) && (jumpsList == null || jumpsList.size() == 0)) {
			int tempV = min(alpha, beta, depth + 1);
			if (tempV > v) {
				v = tempV;
			}
			if (v >= beta)
				return v;
			if (v > alpha)
				alpha = v;
		}
		return v;
	}

	public int min(int alpha, int beta, int depth) {
		nodes++;
		if (nodes % 10000000 == 0)
			System.out.println(nodes);
		// cut-off test
		if (depth > maxDepth) {
			return utility();
		}

		int v = Integer.MAX_VALUE;
		if (testTerminal()) {
			return utility();
		}

		getJumps(humanSide);
		List<Move> moves = null;
		List<List<Move>> jumpsList = null;
		if (jumps.size() == 0)
			moves = getMoves(humanSide);
		else
			jumpsList = jumpsClone();
		// single one-step move
		if (moves != null)
			for (Move m : moves) {
				// make move
				result(m, humanSide);
				// printCheckerBoard("Min", currentConfig);
				int tempV = max(alpha, beta, depth + 1);
				// recover move
				recover(m, humanSide);
				if (tempV < v) {
					v = tempV;
				}
				if (v <= alpha)
					return v;
				if (v < beta)
					beta = v;
			}
		// a series of jumps
		if (jumpsList != null)
			for (List<Move> jump : jumpsList) {
				// make jumps
				result(jump, humanSide);
				// printCheckerBoard("Min", currentConfig);
				int tempV = max(alpha, beta, depth + 1);
				// recover jumps
				recover(jump, humanSide);
				if (tempV < v) {
					v = tempV;
				}
				if (v <= alpha)
					return v;
				if (v < beta)
					beta = v;
			}

		// has no moves
		if ((moves == null || moves.size() == 0) && (jumpsList == null || jumpsList.size() == 0)) {
			int tempV = max(alpha, beta, depth + 1);
			if (tempV < v) {
				v = tempV;
			}
			if (v <= alpha)
				return v;
			if (v < beta)
				beta = v;
		}
		return v;
	}

	// public void printCheckerBoard(String side) {
	// try {
	// out.write(side + ":\n");
	// for (int i = 0; i < 8; i++) {
	// for (int j = 0; j < 8; j++) {
	// if (config.config[i][j] == 0)
	// out.write(" ");
	// else
	// out.write("" + config.config[i][j]);
	// }
	// out.write("\n");
	// }
	// out.flush();
	// } catch (IOException e) {
	// e.printStackTrace();
	// }
	//
	// }

	private boolean testTerminal() {
		int nextI, nextJ;
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				switch (config.config[i][j]) {
				case 0:
					break;

				case 1: // white
					nextI = i + 1;
					nextJ = j - 1;
					if (isLegal(nextI, nextJ)) {
						if (config.config[nextI][nextJ] == 0) {
							return false;
						}
					}
					nextJ = j + 1;
					if (isLegal(nextI, nextJ)) {
						if (config.config[nextI][nextJ] == 0) {
							return false;
						}
					}

					nextI = i + 2;
					nextJ = j - 2;
					if (isLegal(nextI, nextJ)) {
						int midI = (i + nextI) >> 1, midJ = (j + nextJ) >> 1;
						if (config.config[nextI][nextJ] == 0 && config.config[midI][midJ] == 2)
							return false;
					}

					nextJ = j + 2;
					if (isLegal(nextI, nextJ)) {
						int midI = (i + nextI) >> 1, midJ = (j + nextJ) >> 1;
						if (config.config[nextI][nextJ] == 0 && config.config[midI][midJ] == 2)
							return false;
					}
					break;

				case 2:
					nextI = i - 1;
					nextJ = j - 1;
					if (isLegal(nextI, nextJ)) {
						if (config.config[nextI][nextJ] == 0) {
							return false;
						}
					}
					nextJ = j + 1;
					if (isLegal(nextI, nextJ)) {
						if (config.config[nextI][nextJ] == 0) {
							return false;
						}
					}

					nextI = i - 2;
					nextJ = j - 2;
					if (isLegal(nextI, nextJ)) {
						int midI = (i + nextI) >> 1, midJ = (j + nextJ) >> 1;
						if (config.config[nextI][nextJ] == 0 && config.config[midI][midJ] == 1)
							return false;
					}

					nextJ = j + 2;
					if (isLegal(nextI, nextJ)) {
						int midI = (i + nextI) >> 1, midJ = (j + nextJ) >> 1;
						if (config.config[nextI][nextJ] == 0 && config.config[midI][midJ] == 1)
							return false;
					}
					break;
				}
		return true;
	}

	private boolean isLegal(int x, int y) {
		if (y >= 0 && y < 8 && x >= 0 && x < 8)
			return true;
		else
			return false;
	}

	public int utility() {
		int white = 0, black = 0;
		// count for white and black
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				switch (config.config[i][j]) {
				case 0:
					break;
				case 1:
					if (i == 7)
						white += 2;
					else
						white += 1;
					break;
				case 2:
					if (i == 0)
						black += 2;
					else
						black += 1;
					break;
				}
		if (agentSide == Configuration.WHITE) {
			// if (white > black)
			// return 1;
			// else if (white == black)
			// return 0;
			// else
			// return -1;
			return white - black;
		} else {
			// if (black > white)
			// return 1;
			// else if (black == white)
			// return 0;
			// else
			// return -1;
			return black - white;
		}
	}

	public List<List<Move>> jumpsClone() {
		List<List<Move>> l = new ArrayList<List<Move>>();
		for (int i = 0; i < jumps.size(); i++) {
			l.add(jumps.get(i));
		}
		return l;
	}

	public CheckerAgentThread(byte agentSide) {
		super();
		this.agentSide = agentSide;
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				for (int k = 0; k < 8; k++)
					for (int l = 0; l < 8; l++) {
						Move m = new Move(i, j, k, l);
						moves[i][j][k][l] = m;
					}
		// try {
		// out = new BufferedWriter(new OutputStreamWriter(new
		// FileOutputStream("d:/log.txt")));
		// } catch (FileNotFoundException e) {
		// e.printStackTrace();
		// }

	}

	public Configuration getConfig() {
		return config;
	}

	public void setConfig(Configuration config) {
		this.config = config;
	}

	public byte getAgentSide() {
		return agentSide;
	}

	public void setAgentSide(byte agentSide) {
		this.agentSide = agentSide;
	}

	public byte getHumanSide() {
		return humanSide;
	}

	public void setHumanSide(byte humanSide) {
		this.humanSide = humanSide;
	}

	@Override
	public void run() {
		while (true) {
			synchronized (this) {
				try {
					switch (level) {
					case 1:
						maxDepth = EASY;
						break;
					case 2:
						maxDepth = MEDIUM;
						break;
					case 3:
						maxDepth = HARD;
						break;
					case 4:
						maxDepth = SUPERHARD;
						break;
					}
					wait(); // let human play first
					sleep(200);
					this.action();
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}

	public int getLevel() {
		return level;
	}

	public void setLevel(int level) {
		this.level = level;
	}

}
